package com.example.demo.arithmetic.datastructure.tree;

import cn.hutool.core.lang.Console;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Binary Search Tree 二叉查找数
 * key 唯一
 */
public class BSTTree1 {

    // 根节点
    BSTNode root;

    public Object get(int key) {
        return search(root, key);
    }

    /**
     * 非递归实现查找,尾递归转循环遍历 简单
     * 尾递归：
     *
     * @param key
     * @return
     */
    public Object get2(int key) {
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    /**
     * 递归实现查找key对应的value
     *
     * @param curr
     * @param key
     * @return
     */
    private Object search(BSTNode curr, int key) {
        // 找到最后一个节点也没找到
        if (curr == null) {
            return null;
        }
        if (key < curr.key) {
            return search(curr.left, key);
        } else if (key > curr.key) {
            return search(curr.right, key);
        } else {
            // 相等代表找到了
            return curr.value;
        }
    }

    public Object min2() {
        if (root == null) {
            return null;

        }

        BSTNode p = root;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    public Object max() {
        return getMax(root);
    }

    private Object getMax(BSTNode node) {
        if (node == null) {
            return null;
        }
        BSTNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    /**
     * 最小的key对应的值
     *
     * @return
     */
    public Object min() {
        return doMin(root);
    }


    public void put(int key, Object value) {
        BSTNode node = root;
        // 先查找 有的话更新
        //
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                // 找到了 更新旧值
                node.value = value;
                return;
            }
        }
        if (parent == null) {
            root = new BSTNode(key, value);
            return;
        }
        // 没找到 新增
        BSTNode newNode = new BSTNode(key, value);
        if (parent.key > newNode.key) {
            parent.left = newNode;
        } else if (parent.key < newNode.key) {
            parent.right = newNode;
        }
        //return null;
    }


    /**
     * 前驱节点
     * 1.先找到本节点
     * 2.找前驱动节点
     * 节点有左子树，左子树最大值就是前驱节点
     * 没有左子树，离他最近的，自左而来的祖先就是前任
     *
     * @param key
     * @return
     */
    public Object predecessor(int key) {
        BSTNode node = root;
        // 先查找 有的话更新
        BSTNode ancestorFromLeft = null;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                // 往右走 代表是自左而来的
                ancestorFromLeft = node;
                node = node.right;
            } else {
                // 找到了 更新旧值
                break;
            }
        }
        // 没找到节点
        if (node == null) {
            return null;
        }
        if (node.left != null) {
            return getMax(node.left);
        } else {
            // 没有左子树，离他最近的，自左而来的祖先就是前任
            return ancestorFromLeft == null ? null : ancestorFromLeft.value;
        }
    }

    /**
     * 后驱节点
     * 1.先找到本节点
     * 2.找后驱动节点
     * 节点有右子树，右子树最小值就是前驱节点
     * 没有右子树，离他最近的，自右而来的祖先就是前任
     *
     * @param key
     * @return
     */
    public Object successor(int key) {
        BSTNode node = root;
        // 先查找 有的话更新
        BSTNode ancestorFromRight = null;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
                // 往右走 代表是自右而来的
                ancestorFromRight = node;
            } else if (key > node.key) {

                node = node.right;
            } else {
                // 找到了 更新旧值
                break;
            }
        }
        // 没找到节点
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            return doMin(node.right);
        } else {
            // 没有右子树，离他最近的，自右而来的祖先就是前任
            return ancestorFromRight == null ? null : ancestorFromRight.value;
        }
    }

    /**
     * 节点删除
     * (1) 删除的节点只有一个孩子的情况，较为简单
     * 1.删除节点没有左孩子，将右孩子托孤给parent
     * 2.删除节点没有右孩子，将左孩子托孤给parent
     * (2) 两个孩子的情况
     *
     * @param key
     * @return deleted node value
     */
    public Object delete(int key) {
        BSTNode node = root;
        // 记录parent节点
        BSTNode parent = null;
        while (node != null) {
            if (key < node.key) {
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            } else {
                break;
            }
        }
        if (node == null) {
            return null;
        }
        // 只有一个右孩子
        if (node.left == null) {
            shift(parent, node, node.right);
        } else if (node.right == null) {// 只有一个左孩子
            shift(parent, node, node.left);
        } else {//两个孩子的情况
            // 被删除的节点找后继
            BSTNode s = node.right;
            BSTNode sParent = node;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }

            if (sParent != node) {
                shift(sParent, s, s.right);
            }
            shift(parent, node, s);
            s.left = node.left;
        }
        return node.value;

    }

    // 递归 TODO 未完成 太抽象了
    public Object deleteRescuive(int key) {
        root = doDelete(root, key);

        return null;

    }

    private BSTNode doDelete(BSTNode node, int key) {

        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = doDelete(node.left, key);
        } else if (key > node.key) {
            node.right = doDelete(node.right, key);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            } else {
                BSTNode p = node.right;
                while (p.left != null) {
                    p = p.left;
                }
                p.right = doDelete(node.right, p.key);
                p.left = node.left;
                return p;
            }
        }
        return node;
    }

    /**
     * 托孤方法
     */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {

        if (parent == null) {
            // 没有父节点。自己就是新的根节点
            root = child;
        } else if (parent.left == deleted) {
            parent.left = child;
        } else if (parent.right == deleted) {
            parent.right = child;
        }
    }


    /**
     * Finds the minimum value in a binary search tree.
     *
     * @param node the root node of the binary search tree
     * @return the minimum value in the binary search tree, or null if the tree is empty
     */
    private Object doMin(BSTNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }

        return doMin(node.left);
    }


    public List<Object> less(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) { //前进
                stack.push(p);
                p = p.left;
            } else {
                // 往回走
                BSTNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                } else {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

    public List<Object> greater(int key) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) { //前进
                stack.push(p);
                p = p.right;
            } else {
                // 往回走
                BSTNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                } else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }

    public List<Object> between(int key1, int key2) {
        ArrayList<Object> result = new ArrayList<>();
        BSTNode p = root;
        LinkedList<BSTNode> stack = new LinkedList<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) { //前进
                stack.push(p);
                p = p.left;
            } else {
                // 往回走
                BSTNode pop = stack.pop();
                if (pop.key > key1 && pop.key < key2) {
                    result.add(pop.value);
                } else if (key2 < pop.key) {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        BSTTree1 bstTree1 = buildTree();
//        Object o = bstTree1.get(7);
//        Object o1 = bstTree1.get(1);
//        Object o2 = bstTree1.get(3);
//
//        Object o22 = bstTree1.get(7);
//        Object o13 = bstTree1.get(1);
//        Object o24 = bstTree1.get(3);
//        Console.print("{},{},{}", o, o1, o2);
//        System.out.println();
//        Console.print("{},{},{}", o22, o13, o24);
//        System.out.println();
//        System.out.println(bstTree1.min());
//        System.out.println(bstTree1.min2());
//        System.out.println(bstTree1.max());
//        System.out.println(bstTree1.predecessor(7));
        List<Object> less = bstTree1.less(3);
        List<Object> greater = bstTree1.greater(3);
        List<Object> between = bstTree1.between(3, 6);
        System.out.println(Arrays.toString(less.toArray()));
        System.out.println(Arrays.toString(greater.toArray()));
        System.out.println(Arrays.toString(between.toArray()));

    }

    private static BSTTree1 buildTree() {
        BSTNode n1 = new BSTNode(1, "1");
        BSTNode n3 = new BSTNode(3, "3");
        BSTNode n2 = new BSTNode(2, "2", n1, n3);

        BSTNode n5 = new BSTNode(5, "5");
        BSTNode n7 = new BSTNode(7, "7");
        BSTNode n6 = new BSTNode(6, "6", n5, n7);
        BSTNode root = new BSTNode(4, "4", n2, n6);

        BSTTree1 tree1 = new BSTTree1();
        tree1.root = root;
        return tree1;
    }

    static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key = key;
        }

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

    }
}
